package top.lyc829.leetcode.T238;

import java.util.Arrays;

public class Solution {

    /**
     * 解法1：利用两个数组，存储前缀之积和后缀之积，前缀之积乘后缀之积即为当前元素的结果
     *
     * @param nums
     * @return
     */
    public int[] productExceptSelf(int[] nums) {

        int[] L = new int[nums.length];
        int[] R = new int[nums.length];

        L[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            L[i] = L[i - 1] * nums[i - 1];
        }

        R[nums.length - 1] = 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            R[i] = R[i + 1] * nums[i + 1];
        }

        for (int i = 0; i < nums.length; i++) {
            L[i] *= R[i];
        }
        return L;
    }

    /**
     * 解法2，不用R数组，利用变量R动态构造后缀之积
     *
     * @param nums
     * @return
     */
    public int[] productExceptSelf2(int[] nums) {

        int len = nums.length;
        int[] res = new int[len];

        res[0] = 1;
        for (int i = 1; i < len; i++) {
            res[i] = res[i - 1] * nums[i - 1];
        }

        int R = 1;
        for (int i = len - 1; i >= 0; i--) {
            res[i] = res[i] * R;
            R = R * nums[i];
        }

        return res;
    }

    public int[] productExceptSelf3(int[] nums) {
        int len = nums.length;
        int[] leftArray = new int[len];
        int[] rightArray = new int[len];

        leftArray[0] = 1;
        for (int i = 1; i < len; i++) {
            leftArray[i] = leftArray[i - 1] * nums[i - 1];
        }

        rightArray[len - 1] = 1;
        for (int j = len - 2; j >= 0; j--) {
            rightArray[j] = rightArray[j + 1] * nums[j + 1];
        }

        for (int i = 0; i < len; i++) {
            leftArray[i] *= rightArray[i];
        }

        return leftArray;

    }


    public static void main(String[] args) {

        Solution s = new Solution();
        int[] res = s.productExceptSelf3(new int[]{1, 2, 3, 4});
        System.out.println(Arrays.toString(res));
    }

}
